The present invention relates generally to the field of communication systems. More particularly, the present invention relates to communication systems
Two information services found in households and businesses today include television, or video, services and telephone services. Another information service involves digital data transfer which is most frequently accomplished using a modem connected to a telephone service. All further references to telephony herein shall include both telephone services and digital data transfer services.
Characteristics of telephony and video signals are different and therefore telephony and video networks are designed differently as well. For example, telephony information occupies a relatively narrow band when compared to the bandwidth for video signals. In addition, telephony signals are low frequency whereas NTSC standard video signals are transmitted at carrier frequencies greater than 50 MHz Accordingly, telephone transmission networks are relatively narrow band systems which operate at audio frequencies and which typically serve the customer by twisted wire drops from a curb-side junction box. On the other hand, cable television services are broad band and incorporate various frequency carrier mixing methods to achieve signals compatible with conventional very high frequency television receivers. Cable television systems or video services are typically provided by cable television companies through a shielded cable service connection to each individual home or business.
One attempt to combine telephony and video services into a single network is described in U.S. Pat. No. 4,977,593 to Balance entitled xe2x80x9cOptical Communications Network.xe2x80x9d Balance describes a passive optical communications network with an optical source located in a central station. The optical source transmits time division multiplexed optical signals along an optical fiber and which signals are later split by a series of splitters between several individual fibers servicing outstations. The network allows for digital speech data to be transmitted from the outstations to the central station via the same optical path. In addition, Balance indicates that additional wavelengths could be utilized to add services, such as cable television, via digital multiplex to the network.
A 1988 NCTA technical paper, entitled xe2x80x9cFiber Backbone: A Proposal For an Evolutionary Cable TV network Architecture,xe2x80x9d by James A. Chiddix and David M. Pangrac, describes a hybrid optical fiber/coaxial cable television (CATV) system architecture. The architecture builds upon existing coaxial CATV networks. The architecture includes the use of a direct optical fiber path from a head end to a number of feed points in an already existing CATV distribution system.
U.S. Pat. No. 5,153,763 to Pidgeon, entitled xe2x80x9cCATV Distribution Networks Using Light Wave Transmission Lines,xe2x80x9d describes a CATV network for distribution of broad band, multichannel CATV signals from a head end to a plurality of subscribers. Electrical to optical transmitters at the head end and optical to electrical receivers at a fiber node launch and receive optical signals corresponding to broad band CATV electrical signals. Distribution from the fiber node is obtained by transmitting electrical signals along coaxial cable transmission lines. The system reduces distortion of the transmitted broad band CATV signals by block conversion of all or part of the broad band of CATV signals to a frequency range which is less than an octave. Related U.S. Pat. No. 5,262,883 to Pidgeon, entitled xe2x80x9cCATV Distribution Networks Using Light Wave Transmission Lines,xe2x80x9d further describes the distortion reducing system.
Although the above-mentioned networks describe various concepts for transmitting broad band video signals over various architectures, which may include hybrid optical fiber/coax architectures, none of these references describe a cost effective, flexible, communications system for telephony communications. Several problems are inherent in such a communication system.
One such problem is the need to optimize the bandwidth used for transporting data so that the bandwidth used does not exceed the allotted bandwidth. Bandwidth requirements are particularly critical in multi-point to point communication where multiple transmitters at remote units must be accommodated such that allotted bandwidth is not exceeded.
A second problem involves power consumption of the system. The communication system should minimize the power used at the remote units for the transport of data, as the equipment utilized at the remote units for transmission and reception may be supplied by power distributed over the transmission medium of the system.
Another problem arises from a fault in the system preventing communication between a head end and multiple remote units of a multi-point to point system. For example, a cut transmission line from a head end to many remote units may leave many users without service. After the fault is corrected, it is important bring as many remote units back into service as quickly as possible.
Data integrity must also be addressed. Both internal and external interference can degrade the communication. Internal interference exists between data signals being transported over the system. That is, transported data signals over a common communication link may experience interference therebetween, decreasing the integrity of the data Ingress from external sources can also effect the integrity of data transmissions. A telephony communication network is susceptible to xe2x80x9cnoisexe2x80x9d generated by external sources, such as HAM radio. Because such noise can be intermittent and vary in intensity, a method of transporting data over the system should correct or avoid the presence of such ingress.
These problems and others as will become apparent from the description to follow, present a need for an enhanced communication system. Moreover, once the enhanced system is described, a number of practical problems in its physical realization are presented and overcome.
Another embodiment provides a method and apparatus for a fast Fourier transform. This invention relates to the field of electronic communication systems, and more specifically to an improved method and apparatus for providing a fast Fourier transform (xe2x80x9cFFTxe2x80x9d).
There are many advanced digital signal-processing applications requiring analysis of large quantities of data in short time periods, especially where there is interest in providing xe2x80x9creal timexe2x80x9d results. Such applications include signal processing in modems which use OFDM (orthogonal frequency division multiplexing). In order to be useful in these and other applications, Discrete Fourier Transform (DFT) or Fast Fourier Transform (FFT) signal processors must accommodate large numbers of transforms, or amounts of data, in very short processing times, often called high data throughput
In addition to the speed and data-throughput requirements, power consumption is a major concern for many applications. In some signal-processing applications, power is supplied by portable generation or storage equipment, such as batteries, where the ultimate power available is limited by many environment. In such applications, processor power consumption must be as low as possible. One useful measure of utility or merit for FFT processors is the energy dissipation per transform point. Ultimately, one key problem with any FFT processor is the amount of power consumed per transform. Generally, high-performance, efficient FFT processors exhibit energy dissipations per transform in the range of 100 to 1000 times log2N nanojoules, where N is the number of points in a given transform. As a consequence, reasonably large transforms required to process large arrays of data, result in large power consumption.
Machine-implemented computation of an FFT is often simplified by cascading together a series of simple multiply-and-add stages. When a recursive process is used, data circulates through a single stage and the computational structure of the stage is made variable for each circulation. Each circulation through the stage is referred to as a xe2x80x9cpassxe2x80x9d.
A plurality of computational elements, each known as a radix-r butterfly, may be assembled to define a single stage for carrying out a particular pass. A radix-r butterfly receives r input signals and produces a corresponding number of r output signals, where each output signal is the weighted sum of the r input signals. The radix number, r, in essence, defines the number of input components which contribute to each output component.
By way of example, a radix-2 butterfly receives two input signals and produces two output signals. Each output signal is the weighted sum of the two input signals. A radix-4 butterfly receives four input signals and produces four corresponding output signals. Each output signal of the radix-4 butterfly constitutes a weighted sum of the four input signals.
Completion of an N-point Fast Fourier Transform (FFT) requires that the product of the butterfly radix values, taken over the total number of stages or passes, equals the total point count, N. Thus, a 64-point FFT can be performed by one radix-64 butterfly, or three cascaded stages where each stage has sixteen radix-4 butterflies (the product of the radix values for stage-1 and stage-2 and stage-3 is 4xc3x974xc3x974=64), or six cascaded stages where each of the six stages comprises 32 radix-2 butterflies (the product of the radix values for stage-1 through stage-6 is 2xc3x972xc3x972xc3x972=xc3x972=64).
A multi-stage or multi-pass FFT process can be correctly carried out under conditions where the number of butterfly elements changes from one pass (or stage) to the next and the radix value, r, of the butterfly elements also changes from one pass (or stage) to the next. A paper by Gordon DeMuth, xe2x80x9cALGORITHMS FOR DEFINING MIXED RADIX FFT FLOW GRAPHSxe2x80x9d, IEEE Transactions on Acoustics, Speech, and Signal Processing, Vol 37, No. 9, September 1989, Pages 1349-1358, describes a generalized method for performing an FFT with a mixed-radix system. A mixed-radix system is one where the radix value, r, in one stage or pass is different from that of at least one other stage or pass.
An advantage of a mixed-radix computing system is that it can be xe2x80x9ctunedxe2x80x9d to optimize the signal-to-noise ratio of the transform (or more correctly speaking, to minimize the accumulated round-off error of the total transform) for each particular set of circumstances. By way of example, it is advantageous in one environment to perform a 512-point FFT using the mixed-radix sequence: 4, 4, 4, 4, 2. In a different environment, it may be more advantageous to use the mixed-radix sequence: 4, 2, 4, 4, 4. Round-off error varies within a machine of finite precision as a function of radix value and the peak signal magnitudes that develop in each stage or pass.
In addition, it may be advantageous to scale intermediate results between each stage or pass, in order to minimize round-off errors and the problem of overflow. Further, it may be advantageous to vary the amount of scaling performed between each pass, e.g., either to scale by xc2xc between each radix-4 stage or to scale by xc2xd for some stages and xe2x85x9 for other stages.
Heretofore, FFT processors generally fetched data values from their working storage in a serial manner, thus limiting the speed which could be obtained. Further, current FFT processors generally were limited in speed by loading the working storage with input values, then processing the data in the working storage, then unloading the result values.
There are many advanced digital signal-processing applications requiring analysis of large quantities of data in short time periods, especially where there is interest in providing xe2x80x9creal timexe2x80x9d results. Such applications include signal processing in modems which use OFDM (orthogonal frequency division multiplexing).
One need in the art is for an accurate analog-to-digital conversion (ADC) at moderate frequencies having limited bandwidth. One technology known in the art is the xe2x80x9cSigma-Deltaxe2x80x9d ADC which provides very good resolution (high number of bits in the digital result), but only for signals whose converted signal bandwidth is low.
Another need is for an ADC which provides bandwidth-limited digital I and Q signals (representing amplitude and quadrature) for a 200 kHz bandwidth received analog modem signal, wherein the digital result has very high resolution and accuracy.
What is needed is a method and apparatus which addresses the above problems in the art.
Embodiments of the present invention provide a Fast Fourier Transform apparatus and method. In one embodiment, and apparatus for providing a Fast Fourier Transform (FFT) and an inverse FFT is provided. The apparatus comprises a radix-N core. The radix-N core includes at least N multipliers. The radix-N core also includes a twiddle-factor lookup table that stores complex twiddle-factors. The twiddle-factor lookup table is coupled to one input of each of the multipliers. The radix-N core also includes a conversion random access memory (RAM) that stores transform points. The conversion RAM is coupled to another input of each of the multipliers. The radix-N core also includes an array of at least N-times-N adder-subtracter-accumulators.